﻿#include <iostream>
#include <assert.h>
using namespace std;

typedef int STDateType;
class Stack
{
public:
	//初始化
	void Init(int n = 4)
	{
		_a = (STDateType*)malloc(sizeof(STDateType) * n);
		if (_a == nullptr)
		{
			perror("malloc fail!");
			exit(1);
		}

		_capacity = n;
		_top = 0;
	}

	//插入
	void Push(STDateType x)
	{
		//判断是否扩容
		if (_top == _capacity)
		{
			size_t newCapacity = _capacity * 2;
			STDateType* tmp = (STDateType*)realloc(_a, newCapacity * sizeof(STDateType));
			if (tmp == nullptr)
			{
				perror("realloc fail!");
				exit(1);
			}

			_a = tmp;
			_capacity = newCapacity;
		}

		_a[_top++] = x;
	}

	//删除
	void Pop()
	{
		assert(_top > 0);
		--_top;
	}

	//判空
	bool Empty()
	{
		return _top == 0;
	}

	//取栈顶元素
	STDateType Top()
	{
		assert(_top > 0);
		return _a[_top - 1];
	}

	//销毁
	void Destroy()
	{
		free(_a);
		_a = nullptr;
		_capacity = _top = 0;
	}

private:
	//成员变量
	STDateType* _a;
	size_t _capacity;
	size_t _top;
};

// ⽤最新加了构造和析构的C++版本Stack实现
bool isValid(const char* s) {
	Stack st;
	while (*s)
	{
		if (*s == '[' || *s == '(' || *s == '{')
		{
			st.Push(*s);
		}
		else
		{
			// 右括号⽐左括号多，数量匹配问题
			if (st.Empty())
			{
				return false;
			}
			// 栈⾥⾯取左括号
			char top = st.Top();
			st.Pop();

			//顺序不匹配
			if ((*s == ']' && top != '[')
				|| (*s == '}' && top != '{')
				|| (*s == ')' && top != '('))
			{
				return false;
			}
		}
		++s;
	}

	//栈为空，返回真，说明数量都匹配,左括号多，右括号少匹配问题
	return st.Empty();
}

int main()
{
	return 0;
}